#include <iostream>
#include "Student.h"
#include "SortTestHelper.h"
using namespace std;
// 选择排序
template<typename T>
void selectorSort (T arr[] , int len)
{
  for(int i = 0; i < len; i++){
    int minIndex = i;
    for(int j = i + 1; j < len; j++ ){
      if(arr[j] < arr[minIndex]){
        minIndex = j;
      }
    }
    swap(arr[i], arr[minIndex]);
  }
}


// 插入排序,有优先终止循环的机会，性能差的原因是因为需交换的次数过多，而每一次交换是3倍的赋值开销
template<typename T>
void insertSort(T arr[], int len)
{
  for(int i = 1; i < len; i++){
    for(int j = i; j > 0 && arr[j] < arr[j - 1]; j--){
      swap(arr[j], arr[j - 1]);
    }
  }
}
// 优化版本的插入排序，用赋值替代交换
template<typename T>
void advInsertSort(T arr[], int len)
{
  for(int i = 1; i < len; i++){
    T temp = arr[i];
    int j; // 保存T的插入位置
    for(j = i; j > 0 && temp < arr[j - 1]; j--){
      arr[j] = arr[j - 1];
    }
    arr[j] = temp;
  }
}
// 冒泡排序
template<typename T>
void bubleSort(T arr[], int len)
{
  for(int i = 0; i < len - 1; i++){
    for(int j = len; j > i; j--){
      if(arr[j] < arr[j - 1]){
        swap(arr[j],arr[j-1]);
      }
    }
  }
}
// 优化后的冒泡排序，用交换代替
template<typename T>
void advBubleSort(T arr[], int len)
{
  for(int i = 0; i < len - 1; i++){
    T temp = arr[len];
    int j;
    for(j = len; j > i; j--){
      if(temp < arr[j - 1]){
        arr[j] = arr[j - 1];
      }else{
        arr[j] = temp;
        temp = arr[j - 1];
      }
    }
  }
}

int main()
{
  // float arr[10] = { 10, 9.2, 8, 7, 6.3, 5, 4, 3, 2.1, 1 };
  // Student student[4] = { {"D", 40}, {"C", 50}, {"B", 30}, {"A", 90} };
  int n = 10000;
  int* arr = SortTestHelper::generateRandomArray(n,1,10000);
  int* arr2 = SortTestHelper::copyArray(arr,n);
  int* arr3 = SortTestHelper::copyArray(arr,n);
  int* arr4 = SortTestHelper::copyArray(arr,n);
  SortTestHelper::testSort("selection Sort", selectorSort, arr, n);
  SortTestHelper::testSort("advInsert Sort", advInsertSort, arr2, n);
  SortTestHelper::testSort("buble Sort", bubleSort, arr3, n);
  SortTestHelper::testSort("advBuble Sort", advBubleSort, arr4, n);
  // SortTestHelper::testSort("Insert Sort", insertSort, arr2, n);
  // selectorSort(arr, n);
  // SortTestHelper::printArray(arr, n);
  // 释放内存空间
  delete[] arr;
  delete[] arr2;
  return 0;
};